Deutsch-Jozsa Algorithm

• hidden Boolean function f
• input - a string of bits
• output - either 0 or 1

Constant function returns all 0's or all 1's
Balanced function returns 0's for exactly half and 1's for the other half

Classical Solution

• if both f(0,0,0,...) -> 0 and f(1,0,0,...) -> 1, then the function is balanced

Quantum Solution

1. Prepare two quantum registers

• first - n-qubit register(initialised to |0⟩)
• second - one-qubit register(initialised to |1⟩)

2. Apply Hadamard gate to each qubit
3. Apply quantum oracle |x⟩|y⟩ to |x⟩|y⊕f(x)⟩
4. Ignore second single qubit register and apply Hadamard gate to each qubit in first register
5. Measure first register